package _binary_search;

import java.util.Arrays;

/**
 * 1011. 在 D 天内送达包裹的能力
 */
public class No1011 {
    private int[] weights;

    public int shipWithinDays(int[] weights, int days) {
        this.weights = weights;
        int ans = Integer.MAX_VALUE;

        int left = Arrays.stream(weights).max().orElseThrow(), right = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = left + (right - left >> 1);
            int needDays = needDays(mid);
            if (needDays > days) left = mid + 1;
            else {
                right = mid - 1;
                ans = Math.min(mid, ans);
            }
        }
        return ans;
    }

    private int needDays(int load) {
        int days = 0;
        int curLoad = 0;
        for (int weight : weights) {
            curLoad += weight;
            // 如果当前载货量超出最大载货量，则需要将可送走的货物先送走
            if (curLoad >= load) {
                days++;
                // 判断当前载货量是否刚好与最大载货量相等，相等则表示所有货物都可以传送走，否则将本次的货物转交给下一次计算
                curLoad = curLoad == load ? 0 : weight;
            }
        }
        // 判断是否所有货物都已传送完成，若还有剩余则再加一天时间
        return curLoad == 0 ? days : days + 1;
    }
}
